package demo.practice.uf;

/**
 * 并查集  快速查询
 */
public class UFQuickFind {

    int[] parent;

    public UFQuickFind(int size) {
        parent = new int[size];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
    }


    public int findP(int x) {//查询操作，其实是查询  根节点
        if (x < 0 || x >= parent.length)
            return -1;  //或者直接抛出异常

        return parent[x];   //直接返回 parent就可以了，因为所有  连接 的节点parent值都相同
    }

    public void join(int a, int b) {
        int ap = findP(a);
        int bp = findP(b);
        if (ap != bp) {
            for (int i = 0; i < parent.length; i++) {
                if (parent[i] == ap)
                    parent[i] = bp; //修改成相同的 parent
            }
        }
    }

    public boolean isJoined(int a, int b) { //两个节点是否是  连接的
        return findP(a) == findP(b);
    }


}
